home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 11 - 1995 / 11.02 Feb 95 / 11.02 Challenge / rubik.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-11  |  6.6 KB  |  210 lines  |  [TEXT/MMCC]
  1. /*
  2.     Attn: Programmers' Challenge Solution 
  3.         (progchallenge@xplain.com)
  4.     MacTech Programmers Challenge - December 94
  5.  
  6.     SolveRubiksCube
  7.     Copyright (c) 1994  J Robert Boonstra
  8. */
  9. /*
  10.  * Problem Statement:
  11.  * 
  12.  * Solve Rubiks cube, given an initial state by a call to
  13.  * MikeCubeToRubiksCube.  Provide access to solution 
  14.  * progress via RubiksCubeToMikeCube.  Return 1 when cube
  15.  * is solved, 0 after an intermediate move, and -1 if the 
  16.  * cube is unsolvable.
  17.  *
  18.  * Background
  19.  * 
  20.  * Although it hasn't been proven, it is believed that
  21.  * "God's algorithm" for solving the cube requires something
  22.  * like 22 or 23 moves in the worst case.  Back in the 
  23.  * 1970s, when the cube was introduced, Singmaster and
  24.  * Thistlethwaite published solutions that solve the cube 
  25.  * in ~52 moves, and that result has probably been improved
  26.  * upon since then.  (These numbers may count half-turns
  27.  * as a single move instead of two quarter-turn moves - 
  28.  * some people prefer to count that way.)  For those 
  29.  * interested in the cube, there is an active mailing list -
  30.  * send mail to cube-lovers-request@ai.mit.edu for more 
  31.  * info.  In the event that Singmaster, Thistlethwaite, God,
  32.  * or an avid cube-lover don't enter the challenge, we 
  33.  * offer this solution.
  34.  *
  35.  * Solution strategy
  36.  *
  37.  * This solution is based on the now out-of-print book
  38.  * by Don Taylor, entitled "Mastering Rubik's Cube", and
  39.  * sold at the time for the princely sum of $1.95.  While
  40.  * not in any way optimal, the solution in the book has
  41.  * the advantage of being (relatively) easy to remember.
  42.  *
  43.  * We solve the cube using the following steps:
  44.  *
  45.  * 1. Solve the edge cubes in the top layer.
  46.  * 2. Solve the corner cubes in the top layer.
  47.  * 3. Solve the (edge) cubes in the middle layer.
  48.  * 4. Move the corner cubes in the bottom layer to the 
  49.  *    correct position.
  50.  * 5. Orient the bottom layer corner cubes correctly.
  51.  * 6. Move the edge cubes in the bottom layer to the 
  52.  *    correct position.
  53.  * 7. Orient the bottom layer edge cubes correctly.
  54.  *
  55.  * This solution trades a large amount of space (code) for
  56.  * speed.  The operators that transform the cube are coded
  57.  * as macros, rather than as subroutines.  (These macros
  58.  * were generated by an auxiliary program.)
  59.  */   
  60.  
  61. #pragma options(honor_register,assign_registers)
  62.  
  63. #include "rubik.h"
  64. #include "transform.h"
  65.  
  66. char *theMoveP;    /* pointer to stored moves */
  67. char *lastMoveP;   /* pointer to final move */
  68. short firstTime;   /* set to 1 by MikeCubeToRubiksCube */
  69.  
  70. int SolveRubiksCube(register RubiksCube *rub)
  71. {
  72. register unsigned short ch;
  73.   if (firstTime) {
  74. /*
  75.  * First time through, check to see if the cube is legal.
  76.  * Check for existence of the required corners/edges.
  77.  * (We also could check the twist on the corners and the 
  78.  * flip parity on the edges to ensure that the cube is 
  79.  * solvable, but I never got that working.)
  80.  */
  81.       if (!LegalCube(rub)) return(-1);
  82. /*
  83.  * Find complete solution on first call.  Play back on
  84.  * subsequent calls.
  85.  *
  86.  * Initial solution split into subroutine calls to 
  87.  * deal with Symantec C limit on code in one file.
  88.  */
  89.       SolveTopEdgesFR(rub);
  90.       SolveTopEdgesLB(rub);
  91.       if (!SolveTopCorners(rub)) return (-1);
  92.       if (!SolveMiddleLayer(rub)) return (-1);
  93.       if (!SolveBottomCorners(rub)) return (-1);
  94.       if (!SolveBottomEdges(rub)) return (-1);
  95.       firstTime = 0;
  96. /*
  97.  * Restore the initial cube state so that we can play back
  98.  * the moves one at a time.
  99.  */    
  100.       lastMoveP = theMoveP;
  101.       theMoveP = rub->theMove;
  102.       {
  103.         register long *p=(long *)&rub->cubie[0][0];
  104.         register ct=16*8/sizeof(long);
  105.         do {
  106.           *p = *(p+ 16*8/sizeof(long));
  107.           ++p;
  108.         } while (--ct);
  109.       }
  110.   }
  111.   ch = *theMoveP;
  112.   switch (ch) {
  113.     case U: U1move; break;
  114.     case F: F1move; break;
  115.     case L: L1move; break;
  116.     case D: D1move; break;
  117.     case B: B1move; break;
  118.     case R: R1move; break;
  119.     case u: U3move; break;
  120.     case f: F3move; break;
  121.     case l: L3move; break;
  122.     case d: D3move; break;
  123.     case b: B3move; break;
  124.     case r: R3move; break;
  125.     }
  126.   return (lastMoveP == ++theMoveP);
  127. }
  128.  
  129. #define CornerVal(X,Y,Z) \
  130.   ((1<<(X##Y##Z##_##X)) | (1<<X##Y##Z##_##Y) | \
  131.                           (1<<X##Y##Z##_##Z))
  132.  
  133. #define EdgeVal(X,Z) \
  134.   ((1<<(X##Z##_##X)) |  (1<<X##Z##_##Z))
  135.  
  136. #define crn(a,b,c)  ((1<<a) | (1<<b) | (1<<c))
  137. #define edg(a,b)    ((1<<a) | (1<<b))
  138.  
  139. static Boolean LegalCube(RubiksCube *rub)
  140. {
  141. char cubeValues[20];
  142. register long whichCubes=0;
  143. register char *valP;
  144. register short count,theVal;
  145.   
  146. /*
  147.  * Make certain all the necessary corner cubes are there.
  148.  */
  149.   valP = cubeValues;
  150.   *valP++ = CornerVal(U,L,F);
  151.   *valP++ = CornerVal(U,R,F);
  152.   *valP++ = CornerVal(U,L,B);
  153.   *valP++ = CornerVal(U,R,B);
  154.   *valP++ = CornerVal(D,L,F);
  155.   *valP++ = CornerVal(D,R,F);
  156.   *valP++ = CornerVal(D,L,B);
  157.   *valP++ = CornerVal(D,R,B);
  158.   
  159.   valP = cubeValues;
  160.   count=8;
  161.   whichCubes=0;
  162.   do {
  163.     theVal = *valP++;
  164.     if (theVal == crn(U,L,F)) {whichCubes|=0x01; continue;}
  165.     if (theVal == crn(U,R,F)) {whichCubes|=0x02; continue;}
  166.     if (theVal == crn(U,L,B)) {whichCubes|=0x04; continue;}
  167.     if (theVal == crn(U,R,B)) {whichCubes|=0x08; continue;}
  168.     if (theVal == crn(D,L,F)) {whichCubes|=0x10; continue;}
  169.     if (theVal == crn(D,R,F)) {whichCubes|=0x20; continue;}
  170.     if (theVal == crn(D,L,B)) {whichCubes|=0x40; continue;}
  171.     if (theVal == crn(D,R,B)) {whichCubes|=0x80; continue;}
  172.     return false;
  173.   } while (--count);
  174.   if (whichCubes != 0xFF) return false;
  175.  
  176. /*
  177.  * Make certain all the necessary edge cubes are there.
  178.  */
  179.   valP = cubeValues+8;
  180.   *valP++ = EdgeVal(U,L); *valP++ = EdgeVal(U,R);
  181.   *valP++ = EdgeVal(D,L); *valP++ = EdgeVal(D,R);
  182.   *valP++ = EdgeVal(U,F); *valP++ = EdgeVal(U,B);
  183.   *valP++ = EdgeVal(D,F); *valP++ = EdgeVal(D,B);
  184.   *valP++ = EdgeVal(L,F); *valP++ = EdgeVal(L,B);
  185.   *valP++ = EdgeVal(R,F); *valP++ = EdgeVal(R,B);
  186.  
  187.   valP = cubeValues+8;
  188.   count=12;
  189.   whichCubes=0;
  190.   do {
  191.     theVal = *valP++;
  192.     if (theVal == edg(U,L)) {whichCubes|=0x0001; continue;}
  193.     if (theVal == edg(U,R)) {whichCubes|=0x0002; continue;}
  194.     if (theVal == edg(D,L)) {whichCubes|=0x0004; continue;}
  195.     if (theVal == edg(D,R)) {whichCubes|=0x0008; continue;}
  196.     if (theVal == edg(U,F)) {whichCubes|=0x0010; continue;}
  197.     if (theVal == edg(U,B)) {whichCubes|=0x0020; continue;}
  198.     if (theVal == edg(D,F)) {whichCubes|=0x0040; continue;}
  199.     if (theVal == edg(D,B)) {whichCubes|=0x0080; continue;}
  200.     if (theVal == edg(L,F)) {whichCubes|=0x0100; continue;}
  201.     if (theVal == edg(L,B)) {whichCubes|=0x0200; continue;}
  202.     if (theVal == edg(R,F)) {whichCubes|=0x0400; continue;}
  203.     if (theVal == edg(R,B)) {whichCubes|=0x0800; continue;}
  204.     return false;
  205.   } while (--count);
  206.   if (whichCubes != 0xFFF) return false;
  207.  
  208.   return (true);
  209. }
  210.